//
// Description: 124. 二叉树中的最大路径和
// Created by Loading on 2022/5/16.
//

#include <bits/stdc++.h>
#include <Data_Structure_Definition.h>
#include <Utils.h>

using namespace std;

int maxPathSum(TreeNode *root) {
    int res = INT_MIN;

    function<int(TreeNode *)> dfs = [&](TreeNode *node) {
        if (!node) {
            return 0;
        }
        // 递归计算左右节点的最大路径和
        int left = max(dfs(node->left), 0);
        int right = max(dfs(node->right), 0);

        // 计算当前节点的最大路径和，更新结果
        int sum = node->val + left + right;
        res = max(res, sum);
        // 路径只能选择左右节点中较大的一个
        return node->val + max(left, right);
    };

    dfs(root);

    return res;
}

int main() {
    vector<int> nums{-10, 9, 20, -1, -1, 15, 7};
    auto root = generateTreeNode(nums);
    int res = maxPathSum(root);
    cout << res << endl;

    return 0;
}